package leetcode.editor.cn.dsa05_annularLinkedList;
//反转一个单链表。
//
// 示例: 
//
// 输入: 1->2->3->4->5->NULL
//输出: 5->4->3->2->1->NULL 
//
// 进阶: 
//你可以迭代或递归地反转链表。你能否用两种方法解决这道题？ 
// Related Topics 链表 
// 👍 1369 👎 0

public class ReverseLinkedList206 {
    public static void main(String[] args) {
        Solution solution = new ReverseLinkedList206().new Solution();
        ListNode head = null;
        ListNode node = null;
        int[] arr = {1,2,3,4,5};
        for (int val : arr) {
            ListNode listNode = new ReverseLinkedList206().new ListNode(val);
            if (node == null) {
                head = listNode;
                node = listNode;
            }else{
                node.next = listNode;
                node = node.next;
            }
        }
        ListNode listNode = solution.reverseList(head);
        while (listNode != null) {
            System.out.print(listNode.val + "->");
            listNode = listNode.next;
        }
        // 5->4->3->2->1->NULL
        System.out.print("NULL");
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public ListNode reverseList(ListNode head) {
            ListNode prevNode = null; //记录上一个元素的引用
            while (head != null) {
                ListNode curNode = head; //保存当前元素
                head = head.next; // 让head指针前移
                curNode.next = prevNode; //让当前元素的指针指向上一个元素
                prevNode = curNode; //保存当前元素为上一个元素，以便让下一个元素指向
            }
            return prevNode;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}